//给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。 
//
// 你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。 
//
// 
//
// 示例 1： 
//
// 
//输入：[1, 2, 2, 3, 1]
//输出：2
//解释：
//输入数组的度是2，因为元素1和2的出现频数最大，均为2.
//连续子数组里面拥有相同度的有如下所示:
//[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
//最短连续子数组[2, 2]的长度为2，所以返回2.
// 
//
// 示例 2： 
//
// 
//输入：[1,2,2,3,1,4,2]
//输出：6
// 
//
// 
//
// 提示： 
//
// 
// nums.length 在1到 50,000 区间范围内。 
// nums[i] 是一个在 0 到 49,999 范围内的整数。 
// 
// Related Topics 数组 哈希表 
// 👍 350 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    Map map = new HashMap<>();
    int maxNum = 0;
    //填充出现最大次数时的数据
    List<Integer> maxNumList = new ArrayList<>();

    class NumInfo {
        //出现的次数
        int num;
        //第一次出现数组的下标
        int startIndex;
        //最后一次出现数组的下标
        int endIndex;
    }

    public int findShortestSubArray(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            NumInfo numInfo = (NumInfo) map.get(nums[i]);
            //填充NumInfo中的num、startIndex、endIndex
            if (null == numInfo) {
                numInfo = new NumInfo();
                numInfo.num = 1;
                numInfo.startIndex = i;
            } else {
                numInfo.num = numInfo.num + 1;
                numInfo.endIndex = i;
            }
            map.put(nums[i], numInfo);
            //装填maxNumList的数据
            if (numInfo.num == maxNum) {
                maxNumList.add(nums[i]);
            } else if (numInfo.num > maxNum){
                maxNumList.clear();
                maxNumList.add(nums[i]);
                maxNum = numInfo.num;
            }
        }

        if (maxNum == 1) {
            //特殊情况处理
            return 1;
        }

        //最小长度
        int minLen = Integer.MAX_VALUE;
        //最小长度中最短的路径
        for (Integer maxNum: maxNumList) {
            NumInfo numInfo = (NumInfo) map.get(maxNum);
            if (null != numInfo && numInfo.endIndex - numInfo.startIndex < minLen) {
                minLen = numInfo.endIndex - numInfo.startIndex;
            }
        }
        return minLen + 1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
